package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/17 10:02
 */
public class _35_搜索插入位置 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,3,5,6};
        int target = 0;

        System.err.println(getInsertPosition(nums, target));
    }

    private static int getInsertPosition(int[] nums, int target) {
        int lp = 0;
        int rp = nums.length - 1;
        while (lp < rp) {
            int m = lp + (rp - lp) / 2;
            if (nums[m] > target) {
                rp = m - 1;
            } else if (nums[m] < target) {
                lp = m + 1;
            }else{
                return m;
            }
        }
        //若target比左指针大，应该插在其右边就+1，否则肯定小，直接返回lp即可（相等的情况已经return m了~~）
        return nums[lp] < target ? lp + 1 : lp;
    }
}
